package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [890. 查找和替换模式 - 力扣（LeetCode）](https://leetcode.cn/problems/find-and-replace-pattern/submissions/)
 * @since Created by work on 2022/6/12 15:33
 */
public class FindAndReplacePattern {

    /**
     * 暴力解法
     * @param words
     * @param pattern
     * @return
     */
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        int len = words.length;
        String unityPattern = getUnityPattern(pattern);
        List<String> result = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (unityPattern.equals(getUnityPattern(words[i]))) {
                result.add(words[i]);
            }
        }

        return result;
    }

    /**
     * 对所有字符串统一无差别格式化
     * @param pattern
     * @return
     */
    private String getUnityPattern(String pattern) {
        int tag = -1;
        int len = pattern.length();
        Map<Character, Integer> characters = new HashMap<>(16);
        Character key;
        String result = "";
        for (int i = 0; i < len; i++) {
            key= pattern.charAt(i);
            characters.getOrDefault(key, tag+1);
            if (!characters.containsKey(key)) {
                characters.put(key, tag++);
            }
            result = result + characters.get(key);
        }
        return result;
    }

    public List<String> findAndReplacePattern2(String[] words, String pattern) {
        int len = words.length;
        List<String> result = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (match(words[i], pattern)) {
                result.add(words[i]);
            }
        }

        return result;
    }

    private boolean match(String word, String pattern) {
        int length = word.length();
        if (length != pattern.length()) {
            return false;
        }
        Map<Character, Character> charMap = new HashMap<>(16);
        Map<Character, Character> pCharMap = new HashMap<>(16);
        String tranStr = "";
        char ch, pCh;
        for (int i = 0; i < length; i++) {
            ch = word.charAt(i);
            if (charMap.containsKey(ch)) {
                tranStr += charMap.get(ch);
            } else {
                pCh = pattern.charAt(i);
                /**
                 * 如果模式串中的字符已经被映射过, 直接返回false
                 */
                if (pCharMap.containsKey(pCh)) {
                    return false;
                }
                charMap.put(ch, pCh);
                pCharMap.put(pCh, ch);
                tranStr += pCh;
            }
        }
        return tranStr.equals(pattern);
    }
}
